/**
 * @file 	ControlFlowGraph.java
 * 
 * @date 	2/27/2012
 * 
 * @author 	Aaron Alaniz (aaron.a.alaniz@gmail.com)
 * 
 * @brief	This class implements an abstract control flow graph
 * 			type. Using an implicitly defined node class, 
 * 			ControlFlowGraph provides properties and implementation
 * 			to map out source code behavior in the form of a directed
 * 			graph.
 *
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class ControlFlowGraph {
	// invariant: set "nodes" contains all nodes in the graph, i.e., if
	// there is an edge "m->n", both "m" and "n" are in "nodes"
	Set<Node> nodes; // set of nodes
	
	// adjacency set, where each edge has a label (annotation)
	Map<Node, Set<Pair<String, Node>>> edges;
	
	static class Node {
		String classname; // containing class
		String methodname; // containing method
		int id; // unique identifier
		String label; // annotation
			
		public Node(String c, String m, int id, String l) {
			this.classname = c;
			this.methodname = m;
			this.id = id;
			this.label = l;
		}
		
		public Node(String c, String m, int id) {
			this(c, m, id, "");
		}
		
		public String toString() {
			return classname + "." + methodname + ": " + id + " \"" + label + "\"";
		}
		
		public boolean equals(Object o) { // [5 points]
			// postcondition: returns true iff all attributes match (up to "equals")
			
			// verify object is not null
			if (o == null) {
				return false;
			}
			
			// verify classes are the same
			if (o.getClass() != Node.class) {
				return false;
			}
			
			Node n = (Node) o;
			
			return this.classname.equals(n.classname) && this.methodname.equals(n.methodname) && this.id == n.id && this.label.equals(n.label);
		}
		
		public int hashCode() { // [5 points]
			// postcondition: satisfies the hash-code contract
			return this.classname.hashCode() + this.methodname.hashCode() + this.id + this.label.hashCode();
		}
	}
	
	public ControlFlowGraph() {
		nodes = new HashSet<Node>();
		edges = new HashMap<Node, Set<Pair<String, Node>>>();
	}
	
	public void addNode(String c, String m, int id) { // [10 points]
		// postcondition: adds Node(c, m, id) to the set of nodes, and if the
		// node is not previously in the set, updates the adjacency-set
		// representation to map the given node to an empty set
		Node n = new Node(c, m, id);
		
		if (nodes.add(n) != false) {
			edges.put(n, new HashSet<Pair<String, Node>>());  // if node is not present in graph then create a new edge map
		}
	}
	
	// [15 points total for all three addEdge methods]
	public void addEdge(String c1, String m1, int id1, String c2, String m2, int id2, String label) {
		// postcondition: adds edge Node(c1, m1, id1) -> Node(c2, m2, id2) with
		// edge-label "label" to "this"; if any of the two nodes is not
		// already in the set of nodes, the set is updated to include them
		
		// Instantiate new nodes 
		Node n1 = new Node(c1, m1, id1);
		Node n2 = new Node(c2, m2, id2);
		
		// Add to graph (if they are not already present)
		addNode(c1, m1, id1);
		addNode(c2, m2, id2);
	
		// Add edge n1 -> n2
		edges.get(n1).add(new Pair<String, Node>(label, n2)); 
	}
	
	public void addEdge(String c1, String m1, int id1, String c2, String m2, int id2) {
		// postcondition: adds edge Node(c1, m1, id1) -> Node(c2, m2, id2) with empty label
		addEdge(c1, m1, id1, c2, m2, id2, ""); 
	}
	
	public void addEdge(String c, String m, int id1, int id2) {
		// postcondition: adds edge between nodes identified by "id1" and "id2",
		// which are in the same method "m" in class "c"
		addEdge(c, m, id1, c, m, id2);
	}
	

	public boolean reachable(String c1, String m1, int id1, String c2, String m2, int id2) {
		// [15 points]
		// postcondition: returns true iff there is a directed path (of length >= 0) from
		// Node(c1, m1, id1) to Node(c2, m2, id2) in the graph
		
		// Establish start and end points of traversal
		Node start = new Node(c1, m1, id1);
		Node dest = new Node(c2, m2, id2);
		
		// Check for identical start and destination nodes
		if (start.equals(dest) == true) {
			return true;
		}
		
		// Get neighboring nodes of the start node to iterate over
		Set<Pair<String, Node>> neighbors = edges.get(start);
		Iterator<Pair<String, Node>> itr = neighbors.iterator();
		
		while(itr.hasNext()) {
			
			// Extract next neighbor node
			Pair<String, Node> p = itr.next();
			Node n = p.two();
			
			// Do depth-first recursive search for the destination node
			if (n.equals(dest) == false) {
				if (reachable(n.classname, n.methodname, n.id, c2, m2, id2) == true) {
					return true; // found destination node in search
				}
			} else {
				return true; // found destination node
			}
		}
		return false; // did not find destination in neighbors
	}
	

	public boolean allNodesReachable(String c, String m, int id) {
		// postcondition: returns true iff all nodes in "C.m" are reachable
		// from Node(c, m, id)
		/*1:*/ Iterator<Node> it = nodes.iterator();
		/*2:*/ while (it.hasNext()) {
		/*3:*/ 	Node n = it.next();
		/*4:*/ 	if (!reachable(c, m, id, c, m, n.id)) {
		/*5:*/ 		return false;
		/*6:*/ 	}
		/*7:*/ }
		/*8:*/ return true;
	}
	
	public String toString() { // for ControlFlowGraph
		return "#nodes = " + nodes.size() + "\nnodes = " + nodes + "\nedges = " + edges;
	}
}